package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func main() {
	head := makeList()
	fmt.Println("原始链表: ")
	printList(head)

	head = reverseListByRecursion(head)
	fmt.Println("反转后的链表: ")
	printList(head)

	head = reverseList(head)
	fmt.Println("再次反转后的链表: ")
	printList(head)
}

// reverseListByRecursion 反转链表, 递归版本
func reverseListByRecursion(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	node := reverseListByRecursion(head.Next)
	head.Next.Next = head
	head.Next = nil

	return node
}

// reverseList 反转链表
func reverseList(head *ListNode) *ListNode {
	var next, prev *ListNode
	for head != nil {
		next = head.Next
		head.Next = prev
		prev = head
		head = next
	}

	return prev
}

// makeList 生成列表
func makeList() *ListNode {
	head := &ListNode{
		Val: 0,
	}

	node := head
	for i := 1; i < 5; i++ {
		node.Next = &ListNode{
			Val: i,
		}
		node = node.Next
	}

	return head
}

// printList 打印列表结构
func printList(head *ListNode) {
	node := head
	for node != nil {
		fmt.Printf("%d -> ", node.Val)
		node = node.Next
	}

	fmt.Println("Nil")
}
